1. Field of the Invention
This invention relates to full access, non-blocking, and self-routing switching networks.
2. Description of the Prior Art
Most switching networks contain physical switching elements which are joined by links to effect interconnection of the network's input terminals to the network's output terminals. Switching networks that can connect any specific input terminal to any specific output terminal are called full access switching networks. Full access networks that can make requested connections without regard to the already existing connections between input and output terminals are termed non-blocking.
One of the most well known full access, non-blocking, switching networks is the complete N by N single stage crossbar, where each of N inputs can connect to each of N outputs through a physical switching element, also called a crosspoint. There are N.sup.2 crosspoints in such a crossbar switch. Since physical crosspoints have always been relatively expensive, considerable research has been done toward finding topologies that require fewer than N.sup.2 crosspoints and yet achieve the desired switching flexibility. Invariably, those topologies contemplate more than a single switching stage.
V. Benes described a novel multistage switching network construction in his classical book entitled "Mathematical Theory of Connecting Networks and Telephone Traffic," Academic Press, New York, 1965. The Benes network, which is derived by successively decomposing a switching network into smaller switching networks, is a multistage network of interconnected 2 by 2 switch elements. The switching elements, having inputs A and B and outputs C and D, assume one of two states: a "pass-through" state, where inputs A and B are connected to outputs C and D, respectively (A.fwdarw.C and B.fwdarw.D); and a "cross" state, where inputs A and B are connected to outputs D and C, respectively (A.fwdarw.D and B.fwdarw.C). Following the Benes lead, other researchers have differently decomposed the N by N switching network and have created other multistage network topologies--each having its own advantages and disadvantages.
Much of the early use of multistage switching networks has been in connection with telecommunications switching. More recently, such networks have been incorporated in many data processing applications, both as switching networks and as parts of the processing units themselves in parallel processing arrangements. In those data processing applications many of the switching networks are of limited flexibility, serving very specific functions such as shuffling or sorting. Sorting is merely the process of rearranging an unordered sequence of numbers to create an ordered sequence of numbers.
Trying to both improve the speed of concurrent I/O operations in computer systems and employ a minimum number of crosspoints, K. E. Batcher devised a useful digital sorting network. Batcher described his multistage network in a paper entitled "Sorting Networks and their Applications," published in a 1968 Spring Joint Computer Conference Proceedings, pp. 307-314 (also, U.S. Pat. No. 3,428,946 issued Feb. 18, 1969). Basically, the Batcher network comprises interconnected 2 by 2 sorting elements which, like the switching elements in the Benes network, assume either the "pass-through" or a "cross" state. The Batcher sorting elements differ from the Benes elements in that the decision of the state to be assumed is made within the sorting elements themselves based on whether a predetermined portion of the digital signal at input A of the sorting element is greater or smaller than a corresponding portion of the digital signal at input B. This characteristic of the sorting elements makes the Batcher network self-routing.
Batcher points out that his self-routing sorting network can be used as a full access switching network because an input can, in effect, specify a connection to a particular output. The specified connections are made, according to Batcher, by numbering the output lines in order and presenting the desired output address at the input, as part of the input signal. The sorting network sorts the addresses and, by that process, makes a connection from each input line to the desired output line.
In similar work on parallel routing networks, D. H. Lawrie described a network that can switch sorted arrays of signals in an article entitled "Access and Alignment of Data in an Array Processor," Transaction on Computers, Vol. C-24, No. 12, December 1975, pp. 1145-1155. The network (which he called the Omega network) employs "pass-through/cross" switch elements similar to the Batcher elements, and the interconnections between stages or rows of the switching elements form a perfect shuffle. The phrase "shuffle" derives from the familiar shuffling of cards, where the upper half of a deck is separated from the lower half of the deck and the cards of the two half decks are interleaved to reconstitute the full deck. The adjective "perfect" denotes the fact that the interleaving is performed by consistently taking one card from each deck, in order.
The network described by Lawrie differs from the Batcher network in that it switches signals to the specific destinations dictated by the signals, rather than simply sorting the signals in ascending order of destination addresses. The Omega network, then, is not truly a sorting network although each element within the network performs a directed routing operation.
Concurrently with expanding research in the use of digital network in the data processing field, the use of digital networks has been growing in the communications field. Such communications networks require, at a minimum, a wide bandwidth transmission medium, an efficient communications technique, and an effective switching network.
One very promising digital communications technique employs packet switching. In a packet switching environment, the information is processed, transmitted and switched in small packets of digital data and each packet contains, inter alia, a destination address. To make full use of the capabilities inherent in packet switching, the switching network in such a communication system must be very fast and, preferably, self-routing.
Being aware of the switching needs of digital communication networks employing packet switching, and being also aware of the attributes of sorting networks, we came to the realization that the implementation of switching through the use of a self-routing sorting network, like the one described by Batcher, is especially well suited for packet switching applications. The suitability comes foremost from the exceptionally good match between the signal format of the packets and the signal format requirement of the self-routing sorting network. Sorting networks are also inherently capable of high operating speed, which is of prime importance in a packet switching environment where the switching network must assume a different state for each successive set of packets. Thus, we realized that self-routing switching networks could be a real boon to packet switching communications networks.
Unfortunately, the Batcher sorting network, 1ike all other sorting networks, has a serious drawback which prevents it from being used as a full access switching network. Specifically, the Batcher network fails to switch properly when there are inactive output ports (i.e., unsought destinations). Since sorting networks merely rearrange the order of the input signals and thus deal only with the positions of signals relative to the positions of other signals, the only time the Batcher network switches properly is when each and every output port is a destination of one and only one input port signal.
The Omega network, although it attempts to make specific connections, is self-routing and non-blocking for a limited set of permutations. It is self-routing and non-blocking when the input is sorted in ascending order (assuming that its outputs are labeled in ascending order), but fails when there are undefined destinations because the algorithm employed by the switching elements requires specific and unique destination addresses. For the same reason and because of interconnection topology, the Omega network also fails when a particular destination is sought by more than one input signal.